The invention pertains to a method for arranging wire conductors within a limited number of channels within predefined constraints. More specifically, the invention pertains to a method for arranging wire segments within allocated channels in bays between rows of adjacent circuits, or over the circuits when the composition of the circuits does not block wiring channels on that particular level of wiring, and particularly in large-scale integrated circuit devices. Further, the invention pertains to integrated circuit devices constructed in accordance with such a method.
"Bay packing", which is a general term descriptive of the method of the invention and the problem intended to be solved by the invention, is an often-encountered problem in the design of large-scale integrated circuit chips. As depicted in FIG. 1, a large-scale integrated circuit chip 10 is sometimes composed of a number of rows 12 of individual circuits 14 arranged back to back. The areas 16 between adjacent rows 12 of such circuits and an area 18 between adjacent columns of such circuits are known as "bays". It is necessary to make interconnections among the circuits 14 using metal or polysilicon conductive lines or the like, herein included under the term "wire". It is of course possible to arrange such wires in both horizontal and vertical directions and on several different levels separated from one another by an insulating material with connections made between levels through connectors known as "vias". Generally, the wires on any one level are defined to be parallel to one another.
With reference to FIG. 2, because there is only a limited about of space between adjacent rows 12 of circuits 14, the number of possible parallel wires at any one point is limited. The possible locations for laying down these wires are known as "channels", depicted in FIG. 2 by dashed lines and identified by reference numeral 17. Each of these circuits 14 will have one or more terminal pads 20 associated therewith for making connections among the various circuits 14. For instance, to make a connection between the terminal pad 20-1 and the terminal pad 20-2, wires 15-1 and 15-3, indicated by dotted lines, are layed down on a lower level of the bay 16. Then, the wires 15-1 and 15-3, along with other wires on the same level, are covered by a layer of insulating material. The ends of the wires 15-1 and 15-3 are then joined by a wire 15-2 layed down in one of the channels 17 on a second level of the bay. Connections between the ends of the wire 15-2 and the wires 15-1 and 15-3 are made through vias 13-1 and 13-2 which penetrate the insulating layer between the upper and lower wiring levels and make connection therebetween. There will, of course, ordinarily be many more wire segments in a bay than are depicted in FIG. 2. Also, the access wires to the terminal pads can be on a level either above or below the level of the bay being packed.
A convenient way for presenting a bay packing problem is to provide a chart of all wire segments which are to be packed at each level in a particular bay with an indication of where the vias associated with each segment are to be placed and with an indication of the directions from the vias in which extend the connecting wires on the adjacent level or levels. An example of such a chart is shown in FIG. 3. In FIG. 3, vias are shown as boxes and the direction of connecting segments on the next level indicated with arrows. Additionally, the positions of the start and end points along the bay should be specified, which may be done in arbitrary units, with reference to a given start point at one end of the bay.
The objective of any bay packing method is, of course, to position each wire segment in a channel while using the fewest channels when an indeterminant (i.e., variable) number of channels are available in the bay, or using no more channels than are available in the particular bay when a fixed number of channels has previously been assigned to the bay, without overlapping segments or violating other constraints. One such approach, termed "left-edge" packing, is described by A. Hashimoto et al., "Wire Routing by Optimizing Channel Assignment Within Large Apertures", Proceedings of Eighth Design Automation Workshop, 1971, pp. 155-169. In accordance with this technique, a first wire segment is assigned to a channel starting at one end of the bay with the next possible segment from among the list of segments to be packed which can fit into the channel without overlapping segments previously assigned to that channel being assigned next. When no segment if available to assign to the remainder of the channel, the channel is considered finished and the packing of the next channel started. This technique is called "left-edge" packing because one generally proceeds from the channel on one side of the bay (the "left edge") toward the other side of the bay.
A major difficulty with left-edge packing is that there are almost always other factors to be considered in addition to the mere fit of the segments. For instance, if this techique were applied to the chart of segments shown in FIG. 3 (with the "left" being at the top), the result would be as shown in FIG. 4. It may readily be appreciated that this result would be totally unacceptable because, for instance, the perpendicular conductors on the other level of the channel for the right ends of segments D and G would have to be coterminous, thus providing an unwanted shortcircuit between the segments D and G. Such interference between two competing segments is termed a "constraint".
Besides such constraints, the left-edge packing technique suffers from other drawbacks. Specifically, it may be required that particular segments be "attracted" to specific wiring channels, that is, there may be imposed a condition that particular segments occupy specific channels so as to connect to closely adjacent circuits. Such conditions may result in missed connections using left-edge packing. Also, assigning a segment to a specific channel may increase the amount of wire needed on another plane. Via restrictions and other technology rules can also cause problems for left-edge packing. For example, there may be imposed restrictions of no horizontally adjacent vias, no via adjacent a circuit contact unless it is in the same network, no via adjacent a second-level metal line, and no via on top of a circuit contact. Crosstalk between adjacent parallel lines is a further example of a different kind of problem that might also affect packing. Left-edge packing does not adequately handle any of these problems.
Yet further, even if constraints are honored, left-edge packing is disadvantageous in that it does not have any "look-ahead" capability. Without such a capability, the necessarily imposed constraints may cause more than a minimum number of channels to be used. An example of such a situation, as described by B. W. Kernighan et al., "An Optimum Channel-Routing Algorithm for Polycell Layouts of Integrated Circuits, Proceedings of the Tenth Design Automation Workshop, 1973, pp. 50-59, is depicted in FIG. 5 which shows the result of using left-edge packing for packing three segments A, B and C as shown. Because segment A starts first, the left-edge packing method requires that it be packed first. Segment B cannot share the first channel with A because they overlap. Hence, segment B is packed in a separate channel. Segment C is constrained to be below segment B because the right-end connections on the other level would otherwise interfere. Thus, the end result is that three channels have been used. However, it may clearly be seen that by packing segment B first even though it does not start first, the result would be the use of only two channels.
An improvement on the basic left-edge packing technique, as described in the above-mentioned paper by Kernighan et al., extends the left-edge packing technique with the use of the concepts of zones. Zones are used to define sets of segments which can be used for abutments without affecting the total number of channels required. Specifically, some abutments are considered "good enough" to keep the number of necessary channels at a minimum, even through the abutments may not be as close as possible. FIG. 6 is an example of a minimal channel utilization which is obtained using such a technique which does not provide minimal abutments between segments. In FIG. 6, segment D, for instance, could abut more closely with segment A than does segment B, and segment G could abut more closely with segment D than does segment E. But in any of those causes, three channels would still be required.
The zone concept provides alternatives that are equally good in terms of fit, but provides no mechanism for chosing among them. While helpful, this technique is thus not completely adequate. That is, selecting among the alternatives by selecting the one which relieves the most constraints will not always provide the best overall result because channel packing is combinatorial in nature. For instance, it may be more important to pack segment A than segment B in the top channel in the situation shown in FIG. 6, but the combination of segment B with others may give a better total result than any possible combination of segments with segment A for that channel. Thus, the zone concept does not solve the basic difficulties inherent with left-edge packing. For example, the problem presented by FIG. 5 would not be properly handled.
A "branch and bound" approach is also described in the above-mentioned article by Kernighan et al. in which the bay-packing process is viewed as the exploration of a tree structure. At each branch point, one segment is chosen to be packed next. Whenever, a channel is finished, an attempt is made to look ahead to determine the minimum number of channels that must be consumed if the current assignments are to be maintained. If the predicted minimum is not satisfactory, then the assignments already made are reconsidered. The main advantage of this approach is that a satisfactory solution will be found if one exists.
However, the time required for executing channel assignments using the branch and bound approach depends greatly on the time used in looking ahead to predict the channel requirement of the eventual result. If "bad" paths can be recognized early, time can be saved both in pursuing those paths and in backing up. If the objective is to find a minimum solution, considerable exploration may be required since it is difficult to recognize a minimum solution without exploring the whole "tree". Thus, unless the problem is relatively easy, the branch and bound approach is not generally acceptable because of the long time that it requires in order to obtain a minimal, or even satisfactory, solution.
A yet further approach to bay packing is described by K. A. Chen et al., "The Chip Layout Problem: An Automatic Wiring Procedure", Proceeding of the Fourteenth Design Automation Conference, 1977, pp. 298-302. In accordance with the technique described in this article, the affinity of segments for one side of the bay or the other is used as a tie breaker during the assignment process. That is, when there is a choice of segments to assign, preference is given to the one with the most connections to the near side of the bay. This helps to reduce lengths of connecting wires, and in some technologies is important for electrical performance. Also, constraints on remaining segments are reduced, even if these constraints are not explicitly defined and attacked. Yet further, by using affinity for the segments which are packed prior to the perpendicular segments on another plane, the number of channels required on the other plane is reduced. However, important constraints may still remain unsolved while segments with many relatively unimportant connecting segments are packed. This can lead to problems with segments that are later packed.
A "linear assignment" process for assigning segments to channels is also known from the above-discussed Chen et al. article. The basic procedure is to start from one end of the bay and simultaneously make assignments to all channels one "cell" at a time. If a segment has already has been assigned to a particular channel, it is attempted to maintain that segment in the same channel for subsequent cells. The affinity of segments for other channels is also considered and is especially important when circuit contacts are on specific channels. The affinity for one side of the bay or other is also used to shorten the connecting wires. Some lookahead can be used, and decisions are based not only on the current cell but also on the cells to be processed next.
Segments may change channels using this approach. This enables affinities to be satisfied, but is disadvantageous if channel changing increases channel consumption. Also, changing channels often requires additional perpendicular segments to be layed down on different wiring planes. Furthermore, a single connection may require parallel segments on different channels in the same bay. If there is not sufficient space to accommodate such additional conductors, an overflow may occur. If the number of additional channels required could be accurately estimated during global wiring, then that number could be reserved and channel switching more easily accomplished. Unfortunately, there is no quick and accurate method for making such estimates, and thus switching channels without adequate lookahead may impose serious problems.
The article T. Asano et al., "A Wire-Routing Scheme Based on Trunk-Division Methods", IEEE Transactions on Computers, Volume C-26, no. 8, 1977 provides a description of how to handle constraints among segments in bay packing. Cycles of constraints sometimes occur in the initial definition of the bay-packing problem. These require division of a segment or some other solution before the actual bay packing can be successful. FIG. 7 shows an example of such a constraint cycle and one possible solution. In FIG. 7, segment A must be above segment B, segment B must be above segment C, and segment C must be above segment A. It is thus clearly not possible to arrange the segments without interference on the other wiring plane. The solution of such a constraint cycle requires that another definition of the segments be found, typically involving dividing at least one of the segments into two new segments, as shown in the lower portion of FIG. 7 wherein segment A has been divided into two new segments A.sub.1 and A.sub.2.
Long chains of constraints, as illustrated in FIG. 8, can also prevent successful conclusion of the bay-packing problem. In this case, if the segments A to F are arranged in any other order other than what is shown, interference between perpendicular wires on the other wiring plane is unavoidable. Thus, an acceptable method of bay packing must be capable of recognizing and addressing the problems of constraint cycles and long constraint chains so that all segments and constraints are defined and adequately dealt with.
Accordingly, it is an object of the present invention to provide a method for packing wires in channels of bays of large scale integrated circuit devices which avoids all of the above-mentioned drawbacks
More specifically, it is an object of the present invention to provide a bay packing method, and accordingly, an integrated circuit device constructed utilizing such as a bay packing method, in which all types of constraints are honored, and yet a near optimum bay-packing arrangement is rapidly found using the criteria considered important. Often the criteria involves minimizing the bay width.